#include "BinaryHeap.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
细节错误容易引发难以察觉的BUG
H->Elements[i]而非H[i]
*/

struct BinaryHeap {
    int Capacity;
    int Size;
    ElementType* Elements;
};

static void Float(PriorityQueue H, int index);
static void Sink(PriorityQueue H, int index);
static void Swap(ElementType* num1, ElementType* num2);

void TestPriorityQueue() {
    PriorityQueue H = Initialize(NN);

    for (int i = 0; i < NN; i++) {
        srand(i * 100);
        Insert(rand() % 10000, H);
    }
    while (!IsEmpty(H)) {
        printf("%d\t", DeleteMin(H));
    }

    Destroy(H);
}

PriorityQueue Initialize(int MaxElements) {
    PriorityQueue pq = (PriorityQueue)malloc(sizeof(struct BinaryHeap));
    pq->Capacity = MaxElements;
    pq->Size = 0;
    pq->Elements = (ElementType*)malloc(MaxElements * sizeof(ElementType));
    return pq;
}

void Destroy(PriorityQueue H) {
    if (!H)
        return;

    free(H->Elements);
    free(H);
}

static void Swap(ElementType* num1, ElementType* num2) {
    ElementType temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

//注意：若index=0，此时(index-1)/2不对，采用(index+1)/2-1可以解决该问题
static void Float(PriorityQueue H, int index) {
    if (!H)
        return;

    //上浮算法比较简单
    ElementType temp = H->Elements[index];
    int parent = (index + 1) / 2 - 1;
    while (parent >= 0 && H->Elements[parent] > temp) {
        H->Elements[index] = H->Elements[parent];
        index = parent;
        parent = (index + 1) / 2 - 1;
    }
    H->Elements[index] = temp;
}

static void Sink(PriorityQueue H, int index) {
    if (!H)
        return;

    ElementType temp = H->Elements[index];
    int child;
    while (2 * index + 1 < H->Size) {
        //找两子节点的最大值
        child = 2 * index + 1;
        if (2 * index + 2 < H->Size &&
            H->Elements[2 * index + 2] < H->Elements[2 * index + 1])
            child++;
        //判断是否需要下沉
        if (H->Elements[child] < temp)
            H->Elements[index] = H->Elements[child];
        else
            return;

        //找到下沉的下一位置
        index = child;
    }
    H->Elements[index] = temp;
}

void Insert(ElementType x, PriorityQueue H) {
    //大致思路：先判断是否需要扩容，再数组末尾插入新元素，对新元素进行上浮操作
    if (!H)
        return;

    //扩容
    if (IsFull(H)) {
        ElementType* tempArr =
            (ElementType*)malloc(H->Capacity * 2 * sizeof(ElementType));
        for (int i = 0; i < H->Size; i++)
            tempArr[i] = H->Elements[i];
        ElementType* tempPtr = H->Elements;
        H->Elements = tempArr;
        free(tempPtr);
        H->Capacity *= 2;
    }

    //插入的简单实现，集成上浮功能
    int index;
    for (index = ++H->Size;
         (index + 1) / 2 - 1 >= 0 && H->Elements[(index + 1) / 2 - 1] > x;
         index = (index + 1) / 2 - 1)
        H->Elements[index] = H->Elements[(index + 1) / 2 - 1];
    H->Elements[index] = x;

    /*
        //添加数据
        H->Elements[H->Size] = x;
        H->Size++;

        //进行上浮操作
        Float(H, H->Size - 1);
    */
}

ElementType DeleteMin(PriorityQueue H) {
    //大致思路：[0]与[size-1]交换，对[0]元素进行下沉操作，删除并返回[size-1]元素
    if (!H)
        return -10000;

    if (H->Size == 1) {
        ElementType res = H->Elements[0];
        H->Size = 0;
        return res;
    }

    ElementType res = H->Elements[0];
    Swap(&H->Elements[0], &H->Elements[H->Size - 1]);
    H->Size--;
    Sink(H, 0);
    return res;
}

ElementType FindMin(PriorityQueue H) {
    if (!H)
        return -10000;

    return H->Elements[0];
}

int IsEmpty(PriorityQueue H) {
    if (!H)
        return 0;

    return H->Size == 0;
}

int IsFull(PriorityQueue H) {
    if (!H)
        return 0;

    return H->Size == H->Capacity;
}
